#pragma once

#include "LevelListNode.h"
#include "internal/OrderedRootNode.h"
#include "../strings/BaseString.h"
#include "KeyHashMap.h"
#include <vector>

#define STACK_METRICS //

namespace qb{
	namespace base{
		template<typename Key, typename Comparator>
		class OrderedLevelList{
			struct Entry;
			typedef container::CachedObjectPool<Entry> EntryPool;
			typedef container::OrderedRootNode<Entry, Key, Comparator> RootNode;
			typedef typename RootNode::NodeType* NodePtr;
			typedef qb::base::KeyHashMap<Entry, Key> EntryHashMap;
			typedef DoubleLinkList<Entry> EntryQueue;
			struct Entry{
				Entry*	listprev;
				Entry*	listnext;
				Entry*	hashprev;
				Entry*	hashnext;
				Key		key;
				NodePtr	node;
			public:
				Entry() :listnext(nullptr), listprev(nullptr),
					hashnext(nullptr), hashprev(nullptr), key(), node(nullptr){}
				Entry(const Key& k) :listnext(nullptr), listprev(nullptr),
					hashnext(nullptr), hashprev(nullptr), key(k), node(nullptr){}
				~Entry(){ reset(); }
				void reset(){
					listprev = listnext = nullptr;
					hashprev = hashnext = nullptr;
					Key temp;
					std::swap(key, temp);
					node = nullptr;
				}
				void reset(const Key& k){
					key = k;
					node = nullptr;
					hashprev = hashnext = nullptr;
					listprev = listnext = nullptr;
				}
				inline Entry* GetNext()const{ return listnext; }
				inline Entry* GetPrev()const{ return listprev; }
				inline NodePtr GetNode()const{ return node; }
				inline const Key& GetKey()const{ return key; }
				inline void SetNext(Entry* next){ listnext = next; }
				inline void SetPrev(Entry* prev){ listprev = prev; }
				inline void SetNode(NodePtr n){ node = n; };

			};
			class NodeBuilder{
				typedef std::vector<NodePtr> NodePtrVec;
				std::vector<Entry*>		m_entries;
				std::vector<NodePtrVec*>	m_layers;
				int				m_capcity;
				int				m_expect;
			public:
				NodeBuilder():m_capcity(0),m_expect(0){}
				~NodeBuilder(){ Reset(); }
				void Reset()
				{
					for (int i = 0; i <(int) m_layers.size(); i++)
					{
						NodePtrVec* layer = m_layers[i];
						if (layer){ layer->clear(); delete layer; }
					}
					m_layers.clear();
					m_entries.clear();
				}
				void Begin(int capcity,int nexpect){
					Reset();
					m_capcity = capcity;
					m_expect = nexpect;
					m_entries.clear();m_entries.reserve(capcity);
					m_layers.clear();
				}
				inline void Add(Entry* entry){ m_entries.push_back(entry);  }
				void Build(RootNode& root, EntryHashMap& hashmap)
				{
					int nsize = m_entries.size();
					if (nsize <= 0)
					{
						Reset();
						return;
					}
					int nloop = nsize / m_expect;
					int nleft = nsize - nloop*m_expect;
					NodePtrVec* layer = new NodePtrVec;
					layer->reserve(nloop + 1);
					m_layers.push_back(layer);
					Entry** parray = &m_entries[0];
					Entry* prev = parray[0];
					hashmap.Insert(prev, prev->key.GetHash());
					for (int i = 1; i < nsize; ++i)
					{
						Entry* et = parray[i];
						prev->SetNext(et);
						et->SetPrev(prev);
						prev = et;
						hashmap.Insert(et, et->key.GetHash());
					}

					//针对m_entries数组,每间隔m_expect个构造一个节点NodePtr来管理
					int base = 0;
					for (int i = 0; i < nloop; i++, base+=m_expect)
					{
						NodePtr node = root.Alloc();
						node->m_entry = parray[base];
						node->m_count = m_expect;
						layer->push_back(node);
						for (int k = 0; k < m_expect; k++)
							parray[base + k]->SetNode(node);
					}
					if (nleft > 0)
					{
						NodePtr node = root.Alloc();
						node->m_entry = m_entries[base];
						node->m_count = nleft;
						layer->push_back(node);
						for (int k = 0; k < nleft; k++)
							m_entries[base + k]->SetNode(node);
					}
					while (m_layers.size() > 0)
					{
						NodePtrVec* lastlayer = m_layers.at(m_layers.size() - 1);
						if (lastlayer->size() <= 1)
							break;
						BuildNodeLayer(root, *lastlayer);
					}
					NodePtrVec* lastlayer = m_layers.at(m_layers.size() - 1);
					DEBUG_ASSERT(lastlayer->size() == 1);
					NodePtr newroot = lastlayer->at(0);
					Entry* tail = m_entries.at(nsize - 1);
					root.SwapRoot(newroot, tail);
					root.Free(newroot);
					Reset();
				}
				void BuildNodeLayer(RootNode& root, const NodePtrVec& layer)
				{
					//针对节点层,每间隔m_expect个构造一个节点NodePtr来管理该层的节点
					//新建节点又构成新的层
					DEBUG_ASSERT(layer.size() > 0);
					int nloop = layer.size() / m_expect;
					int nleft = layer.size() - nloop*m_expect;
					NodePtrVec* sublayer = new std::vector<NodePtr >;
					m_layers.push_back(sublayer);
					sublayer->reserve(nloop + 1);
					for (int i = 0; i <= nloop; i++)
					{
						if (i == nloop && nleft <= 0)break;
						NodePtr node = root.Alloc();
						int base = i*m_expect;
						int count = 0;
						int kcount = i == nloop ? nleft:m_expect;
						for (int k = 0; k < kcount; k++)
						{
							NodePtr child = layer[base + k];
							child->m_parent = node;
							count += child->m_count;
							node->m_queue.Append(child);
						}
						node->m_count = count;
						sublayer->push_back(node);
					}
				}
			};
		public:
			typedef typename container::IteratorBase<Entry, Key> iterator;
		protected:
			EntryHashMap	m_hashmap;
			RootNode		m_root;
			NodeBuilder		m_builder;
			Comparator*		m_comparator;
			EntryPool		m_entry_pool;
			double			m_cmp_sum;
			double			m_find_count;
			Key				m_blank;
		public:
			OrderedLevelList() :m_root(30), m_comparator(new Comparator()),
				m_find_count(0), m_cmp_sum(0)
			{

			}
			~OrderedLevelList()
			{
				clear();
				if (m_comparator)
					delete m_comparator;
				m_comparator = nullptr;
			}
			void set_comparator(Comparator* comp){
				if (m_comparator && m_comparator != comp)
					delete m_comparator;
				m_comparator = comp;
			}
			void set_option(const char* name, const char* value)
			{
				if (strcmp(name, "root_expect") == 0){ m_root.set_expect(atoi(value)); }
				else if (strcmp(name, "node_max") == 0){ m_root.set_max(atoi(value)); }
				else if (strcmp(name, "hash_length") == 0){
					m_hashmap.Expand(atoi(value));
				}
			}
			void reserve(int n)
			{
				m_hashmap.Expand(n);
				n -= m_root.size();
				if (n > 0)m_entry_pool.Reserve(n);
			}
			bool check_node(bool recursive)const
			{
				// 增强尺寸检查
				if (m_hashmap.GetCount() != m_root.size())
				{
					int n1 = m_hashmap.GetCount();
					int n2 = m_root.size();
					int n3 = 0;
					int n4 = m_hashmap.CalcCount();
					Entry* found = nullptr;
					Entry* head = nullptr;
					DEBUG_ASSERT(n1 == n2);
					DEBUG_ASSERT(n1 == n4);
					if (n1!=n2)
					{
						std::set<Key> temp;
						class EntryHashMapClone : public EntryHashMap::Listener{
							std::set<Key>&	m_dest;
							int				m_error;
						public:
							EntryHashMapClone(std::set<Key>& dest) :m_dest(dest), m_error(0){}
							virtual void OnEntry(Entry* entry, int slot){
								if (m_dest.find(entry->key) == m_dest.end())
									m_dest.insert(entry->key);
								else{
									m_error++;
								}
							}
						} cloneListener(temp);
						m_hashmap.Enum(&cloneListener);
						DEBUG_ASSERT(temp.size() == n1);
						head = m_root.GetFirstEntry();
						while (head)
						{
							found = m_hashmap.Find(head->key, head->key.GetHash());
							DEBUG_ASSERT(found == head);
							head = head->GetNext();
							n3++;
						}
						DEBUG_ASSERT(n3 == n2 && n3==n1);
					}
				}
				if (recursive)
				{
					int nsize = m_root.size();
					const Entry* prev = m_root.at(0);
					for (int i = 1; i < nsize; i++)
					{
						const Entry* cur = prev->GetNext();
						DEBUG_ASSERT(cur && (*m_comparator)(prev->key, cur->key) <= 0);
						prev = cur;
					}
				}
				return m_root.check(recursive);
			}
			void dump(){ 
				int nentry = m_root.size();
				int npool = m_entry_pool.GetCount();
				
				// 打印哈希表状态,空洞,最长,平均,超过1个的
				int nhole = 0, nmax = 0, nsum = 0, nmulti = 0;
				for (int i = 0; i < m_hashmap.GetLength(); i++)
				{
					Entry* head = m_hashmap.GetSlot(i);
					if (head == nullptr)nhole++;
					int nlen = 0;
					while (head)
					{
						nlen++;
						head = head->hashnext;
					}
					nsum += nlen;
					nmulti += nlen > 1 ? 1 : 0;
					nmax = nmax < nlen ? nlen : nmax;
				}
				BLOGINFO("[ActionStater]EntryTree:%8d  EntryPool:%8d EntryTotal:%8d memory:%8d  hashmap:hole:%6d multi:%6d max:%6d avg:%6.2f length:%6d  count:%6d",
					nentry, npool, nentry + npool, (nentry + npool)*sizeof(Entry),
					nhole,nmulti, nmax, m_hashmap.GetCount()*1.0/(m_hashmap.GetLength()-nhole),
					m_hashmap.GetLength(),m_hashmap.GetCount()
					); 
				//m_root.print();
			}
			int64_t get_comp_count(){
				return m_comparator->get_count();
				//return (__int64)m_cmp_sum / m_find_count;
			}
		protected:
			Entry* erase_impl(const Key& k, unsigned int hash, bool check)
			{
				Entry* exist = m_hashmap.Remove(k, hash);
				if (exist)
				{
					m_root.erase(exist, m_comparator, check);
				}
				DEBUG_ASSERT(!check || check_node(false));
				return exist;
			}
		public:
			void update(const std::vector<Key>& keys, const std::vector<bool>& addOrErase)
			{
				// 此批量数据keys对应的真实数据已经更新,刺客检查顺序很可能有不满足的情况,合理
				// DEBUG_ASSERT(check_node(false));
				for (int i = 0; i < (int)keys.size(); i++)
				{
					erase(keys[i],false);
				}

				// 此刻,已经更新的批量数据已经从容器中删除,容器其他的数据必当是有序的
				DEBUG_ASSERT(check_node(true));
				StackArray<Entry*, 64> entries;
				for (int i = 0; i < (int)keys.size(); i++)
				{
					if (addOrErase[i])
					{
						const Key& k = keys[i];
						unsigned int hash = k.GetHash();
						Entry* efound = m_entry_pool.Alloc();
						efound->reset(k);
						m_hashmap.Insert(efound, hash);
						m_root.insert(efound, m_comparator,nullptr);
						entries.Add(efound);
					}
				}
				if (check_entries(entries.GetBuf(), entries.size()))
					rebuild();
				DEBUG_ASSERT(check_node(true));
			}
		protected:
			bool check_entries(Entry** entries, int nsize)
			{
				int nok = 0;
				for (int i = 0; i < nsize; i++)
				{
					Entry* efound = entries[i];
					if (efound->GetNode() == nullptr)
						break;
					NodePtr node = efound->GetNode();
					if (!m_root.check_node_sorted(node, m_comparator, true))
						break;
					nok++;
				}
				return nok < nsize;
			}
			void rebuild()
			{
				if (size() <= 1)
					return;
				DEBUG_ASSERT(0);
				std::vector<Key> keys;
				keys.reserve(size());
				Entry* first = m_root.GetFirstEntry();
				while (first)
				{
					keys.push_back(first->key);
					first = first->GetNext();
				}
				std::sort(keys.begin(), keys.end(), Comparator(*m_comparator));
				clear();
				begin_push(keys.size());
				for (int i = 0; i < (int)keys.size(); i++)
				{
					push(keys[i]);
				}
				end_push();
				DEBUG_ASSERT(check_node(true));
			}
		public:
			bool insert(const Key& k)
			{
				STACK_METRICS("hash:%d/%d",m_hashmap.GetCount(),m_hashmap.GetLength());
				unsigned int hash = k.GetHash();
				// 检查k对应值是否变化,无变化,不用更改位置,相对于删除再插入可提升50倍性能
				Entry* efound = m_hashmap.Find(k, hash);
				Entry* prev = efound ? efound->GetPrev() : nullptr;
				Entry* next = efound ? efound->GetNext() : nullptr;
				if (efound && prev && next)
				{
					if ((*m_comparator)(prev->key, k) < 0 &&
						(*m_comparator)(k, next->key) <= 0)
					{
						DEBUG_ASSERT(check_node(false));
						return true;
					}
				}

				if (efound == nullptr)
				{
					efound = m_entry_pool.Alloc();
					efound->reset(k);
					STACK_METRICS("insert&insert");
					m_hashmap.Insert(efound, hash);
					m_root.insert(efound, m_comparator, next ? next : prev);
				}
				else
				{
					// 已经存在,key没有改变,不需要更新哈希表
					STACK_METRICS("erase&insert");
					m_root.erase(efound,m_comparator);
					m_root.insert(efound, m_comparator);
				}
				DEBUG_ASSERT(check_node(false));
				//BLOGINFO("[CHECK]insert key efound:0x%8x", efound);
				return true;
			}
			bool erase(const Key& k,bool check=true)
			{
				unsigned int hash = k.GetHash();
				Entry* exist = erase_impl(k, hash, check);
				if (exist)
				{
					CHECK_SINGLE(exist);
					DEBUG_ASSERT(!check || check_node(false));
					DEBUG_ASSERT(exist->hashprev == nullptr && exist->hashprev == nullptr);
					//BLOGINFO("[CHECK]erase key exist:0x%8x", exist);
					m_entry_pool.Free(exist);
					return true;
				}
				DEBUG_ASSERT(!check || check_node(false));
				//BLOGINFO("[CHECK]erase key exist:null");
				return false;
			}
		public:
			bool exist(const Key& k)
			{
				unsigned int hash = k.GetHash();
				return m_hashmap.Find(k, hash) != nullptr;
			}
			int  find(const Key& k)
			{
				unsigned int hash = k.GetHash();
				Entry* exist = m_hashmap.Find(k, hash);
				if (exist)
					return m_root.find(exist);
				return -1;
			}
			int  size()const{
				DEBUG_ASSERT(check_node(false));
				return m_root.size();
			}
			const Key& at(int index)
			{
				Entry* et = m_root.at(index);
				return et ? et->GetKey() : m_blank;
			}
			int  get(int index, int count, Key* keys, int* pos = nullptr)
			{
				int ntotal = size();
				int start = index <= 0 ? 0 : index;
				int end = start + count;
				end = end >= ntotal ? ntotal : end;
				start = end - count;
				start = start <= 0 ? 0 : start;
				DEBUG_ASSERT(end - start <= count && end <= ntotal && start >= 0);
				Entry* et = m_root.at(start);
				int i = 0;
				for (; et && i < end - start; i++)
				{
					keys[i] = et->GetKey();
					et = et->GetNext();
				}
				if (pos)*pos = start;
				return i;
			}
			void clear()
			{
				Entry* head = m_root.at(0);
				while (head)
				{
					Entry* temp = head;
					head = head->GetNext();
					temp->SetNode(nullptr); temp->SetNext(nullptr); temp->SetPrev(nullptr);
					m_entry_pool.Free(temp);
				}
				m_hashmap.Clear();
				m_root.destroy();
			}
			void begin_push(int capcity){ 
				clear(); 
				m_builder.Begin(capcity, m_root.get_expect());
			}
			void push(const Key& k){
				// 外界负责k的有序性,注释的代码是通过常规的插入接口来保持k队列的有序性
				// 测试表明,先外界排序然后通过begin_push/push/end_push接口,可以提升速度
				Entry* et = m_entry_pool.Alloc();
				et->reset(k);
				m_builder.Add(et);
				/*unsigned int hash = k.GetHash();
				Entry* exist = m_hashmap.Find(k, hash);
				if (exist == nullptr)
				{
					exist = m_entry_pool.Alloc();
					exist->key = k;
					m_hashmap.Insert(exist, hash);
					m_root.append(exist,m_comparator);
				}*/
			}
			void end_push(){
				m_builder.Build(m_root,m_hashmap);
				DEBUG_ASSERT(check_node(false));
			}
			iterator begin(){ return iterator(0, m_root.at(0)); }
			iterator end(){ return iterator(-1, nullptr); }
		};
	}
}
